package hot100.双指针.单行到底.窗口.哈希.会变窗口;

/** 3-无重复字符的最长子串
/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
 * 输入: s = "abcabcbb"
 * 输出: 3
 *
 * 求字符串里 不重复的 连续的子字符串们中 最大的那一个 的长度
 *
 * tail一直走 调整head ps:计算//调整问题
 * error: 记录是否出现然后有重复就更新到tail位置 ×
 * operation: string索引字符方法 char底层性质与int会自动转换
 */
public class longestNoRepeatSubstring3 {

    public int normalMethod(String s) {
        int resultLength = 0;

        int head = 0;
        int[] lastShowTable = new int[128];
        for(int i=0;i<128;i++){ lastShowTable[i] = -1;}
        for (int i = 0; i < s.length(); i++) {
            /**head-tail重合表达版(head当前元素索引) 需要考虑单个字符开头问题 支持结尾**/
            if (lastShowTable[s.charAt(i)] >= head) {
                head = lastShowTable[s.charAt(i)] +1;
            }

            lastShowTable[s.charAt(i)] = i;

            if (i-head +1> resultLength) {
                resultLength = i-head +1;
            }
            /**                                                           (&& lastShowTable[s.charAt(i)] > -2)
             * tail -head不重合表达版(head当前元素索引-1) 需要考虑单个字符开头问题(如此: head = -1然后table默认为-2) 支持结尾**/
            /*if (lastShowTable[s.charAt(i)] > head) {
                head = lastShowTable[s.charAt(i)];
            }

            lastShowTable[s.charAt(i)] = i;

            if (i-head > resultLength) {
                resultLength = i-head;
            }*/
        }

        return resultLength;
    }

    // 不推荐此 不符合一般的《窗口逻辑》
    public int fuckAccidentalUnderstand(String s) {
        int result = 0;

        int[] headNextStartIndex = new int[128];
        int head = 0;

        //本char在表中索引 ->上次出现的位置 ->更新本段 ->计算长度
        for (int tail=0; tail<s.length(); tail++) {
            // 由于char与int特性 不需要手动计算索引
            /*int index = s.charAt(tail) - 'a';
            int location = lastShowLocationTable[index];*/
            //更改head
            head = Math.max(head, headNextStartIndex[s.charAt(tail)]);
            //若重复,则head的下一个起始点
            headNextStartIndex[s.charAt(tail)] = tail +1;
            //长度
            result = Math.max(result, tail - head +1);

            /** head0 -(某)字符第一次出现 -(某)字符第二次出现 lastShowIndexTable只支持后两者
             *   ->把修改操作延后到下一次重复 使head-first 成立【+1后移】; 基于迭代,当tail=numLength是重复char 长度计算不会被影响
             * **/
            /*head = Math.max(head, lastShowIndexTable[s.charAt(tail)] +1);
            lastShowIndexTable[s.charAt(tail)] = tail;
            result = Math.max(result, tail - head +1);*/
        }
        return result;
    }


    public void charAndIntTest() {
        // int ->char
        int test = ' ';
        System.out.println(test);

        // char ->int
        for (int i=0; i<128; i++){
            System.out.print((char)i + ",");
        }
    }

    public static void main(String[] args) {
        longestNoRepeatSubstring3 solution = new longestNoRepeatSubstring3();
        System.out.println(solution.normalMethod("abcabcbb"));
    }
}